package com.chengzhi.structure;

import com.sun.org.apache.xml.internal.utils.IntStack;

import java.util.Arrays;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

/**
 * @description:
 * @author: ruanchengzhi
 * @create: 2020-07-30 16:17
 **/
public class SortTest {

    public static void main(String[] args) {
        /*int[] arr = {111, 3, 5, 52, 74, 312, 75, 3, 764, 3, 2111, 7, 31};
        mergeSort(arr);
        System.out.println(arr);*/
        int length = 10;
        int[] arr = new int[length];
        for (int i = 0; i < 10; i++) {
            arr[i] = length--;
        }
//        System.out.println(intStream.boxed().collect(Collectors.toList()));
//        System.out.println(intStream.boxed().collect(Collectors.summingInt(t -> t)));
//        StopWatch.run(() -> bubbleSort(arr), time -> System.out.println(time));
//        StopWatch.run(() -> selectionSort(arr), time -> System.out.println(time));
//        StopWatch.run(() -> insertionSort(arr), time -> System.out.println(time));
//        StopWatch.run(() -> shellSort(arr), time -> System.out.println(time));
//        StopWatch.run(() -> mergeSort(arr), time -> System.out.println(time));
//        StopWatch.run(() -> quickSort(arr), time -> System.out.println(time));
        StopWatch.run(() -> buildMaxHeap(arr), time -> System.out.println(time));
        System.out.println(arr);
    }

    /**
     * 冒泡排序 O(n^2)
     *
     * @param arr
     * @return: void
     * @author: ruanchengzhi
     * @date: 2020/7/30
     */
    public static void bubbleSort(int[] arr) {
        int length = arr.length;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }

    }

    /**
     * 选择排序 O(n^2)
     * 循环找到索引最小的下标进行替换
     *
     * @param arr
     * @return: void
     * @author: ruanchengzhi
     * @date: 2020/7/30
     */
    public static void selectionSort(int[] arr) {
        int length = arr.length;
        int minIndex, temp;
        for (int i = 0; i < length; i++) {
            minIndex = i;
            for (int j = i + 1; j < length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    /**
     * 插入排序 O(n^2)
     * 插入元素和之前元素相比
     *
     * @param arr
     * @return: void
     * @author: ruanchengzhi
     * @date: 2020/7/30
     */
    public static void insertionSort(int[] arr) {
        int length = arr.length;
        int cur, preIndex;
        for (int i = 1; i < length; i++) {
            cur = arr[i];
            preIndex = i - 1;
            while (preIndex != 0 && arr[preIndex] > cur) {
                arr[preIndex + 1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex + 1] = cur;
        }
    }

    /**
     * 希尔排序 O(n^1.3)
     *
     * @param arr
     * @return: void
     * @author: ruanchengzhi
     * @date: 2020/7/30
     */
    public static void shellSort(int[] arr) {
        //step:步长
        for (int step = arr.length / 2; step > 0; step /= 2) {
            //对一个步长区间进行比较 [step,arr.length)
            for (int i = step; i < arr.length; i++) {
                int value = arr[i];
                int j;
                //对步长区间中具体的元素进行比较
                for (j = i - step; j >= 0 && arr[j] > value; j -= step) {
                    //j为左区间的取值，j+step为右区间与左区间的对应值。
                    arr[j + step] = arr[j];
                }
                //此时step为一个负数，[j + step]为左区间上的初始交换值
                arr[j + step] = value;
            }
        }

    }

    /**
     * 归并排序 O(nlog2n)
     * 利用分治思想 将已有序的子序列合并，得到完全有序的序列
     *
     * @param arr
     * @return: void
     * @author: ruanchengzhi
     * @date: 2020/7/30
     */
    public static void mergeSort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            mergeSortMerge(arr, left, mid, right);
        }


    }

    public static void mergeSortMerge(int[] arr, int left, int mid, int right) {
        int[] tmp = new int[right - left + 1];

        int i = 0;
        //左边序列和右边序列起始索引
        int j = left, k = mid + 1;
        while (j <= mid && k <= right) {
            if (arr[j] < arr[k]) {
                tmp[i++] = arr[j++];
            } else {
                tmp[i++] = arr[k++];
            }
        }
        //若左边序列还有剩余，则将其全部拷贝进tmp[]中
        while (j <= mid) {
            tmp[i++] = arr[j++];
        }
        //若右边边序列还有剩余，则将其全部拷贝进tmp[]中
        while (k <= right) {
            tmp[i++] = arr[k++];
        }

        for (int t = 0; t < i; t++) {
            arr[left + t] = tmp[t];
        }
    }

    /**
     * 快排 O(nlog2n)
     *
     * @param arr
     * @return: void
     * @author: ruanchengzhi
     * @date: 2020/7/30
     */
    public static void quickSort(int[] arr) {
        quickSort(0, arr.length - 1, arr);
    }

    private static void quickSort(int left, int right, int[] arr) {
        if (left > right) {
            return;
        }
        int temp = arr[left];
        int i = left, j = right;
        while (i < j) {
            while (arr[j] >= temp && i < j) {
                j--;
            }
            while (arr[i] <= temp && i < j) {
                i++;
            }
            if (i < j) {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        arr[left] = arr[i];
        arr[i] = temp;
        quickSort(left, i - 1, arr);
        quickSort(i + 1, right, arr);
    }

    /**
     * 堆排序 O(nlog2n)
     *
     * @param arr
     * @return: void
     * @author: ruanchengzhi
     * @date: 2020/7/30
     */
    public static void buildMaxHeap(int[] arr) {
        MaxHeap<Integer> maxHeap = new MaxHeap<>(arr.length);
        for (int i = 0; i < arr.length; i++) {
            maxHeap.add(arr[i]);
        }

        System.out.println(maxHeap);
    }

    /**
     * 计数排序 O(n+k)
     *
     * @param arr
     * @return: void
     * @author: ruanchengzhi
     * @date: 2020/7/30
     */
    public void countingSort(int[] arr) {

    }

    /**
     * 桶排序 O(n+k)
     *
     * @param arr
     * @return: void
     * @author: ruanchengzhi
     * @date: 2020/7/30
     */
    public void bucketSort(int[] arr) {

    }

    /**
     * 基数排序 O(n*k)
     *
     * @param arr
     * @return: void
     * @author: ruanchengzhi
     * @date: 2020/7/30
     */
    public void radixSort(int[] arr) {

    }


}
